package leetcode

import (
	"fmt"
	"math"
)

type enum int

const ( // iota is reset to 0
	white enum = iota // white == 0
	gray  enum = iota // gray == 1
	black enum = iota // black == 2
)

//Vertex is vertex of graph
type Vertex struct {
	id    int
	color enum
	pre   *Vertex
}

func newVertex(id int) *Vertex {
	return &Vertex{
		id,
		white,
		nil,
	}
}

//Edge is edge of graph
type Edge struct {
	from int
	to   int
}

func newEdge(fromID int, toID int) *Edge {
	return &Edge{
		fromID,
		toID,
	}
}

//Graph is graph
type Graph struct {
	vetexMap map[int]*Vertex
	edgeMap  map[string]*Edge
}

func newGraph() *Graph {
	return &Graph{
		make(map[int]*Vertex),
		make(map[string]*Edge),
	}
}

//EvalKey return edge key by id
func EvalKey(xid int, yid int) string {
	var bid int
	var eid int
	if xid < yid {
		bid = xid
		eid = yid
	} else {
		eid = xid
		bid = yid
	}
	key := fmt.Sprintf("%d-%d", bid, eid)
	return key
}

//AddVertex add edge to graph
func (g *Graph) AddVertex(id int) {
	if _, ok := g.vetexMap[id]; !ok {
		g.vetexMap[id] = newVertex(id)
	}
}

//AddEdge add edge to graph
func (g *Graph) AddEdge(fromID int, toID int) {
	key := EvalKey(fromID, toID)
	if _, ok := g.edgeMap[key]; !ok {
		g.AddVertex(fromID)
		g.AddVertex(toID)
		g.edgeMap[key] = newEdge(fromID, toID)
	}
}

//HasVertex check id is in graph
func (g *Graph) HasVertex(id int) bool {
	if _, ok := g.vetexMap[id]; ok {
		return true
	}

	return false
}

//HasRelation check id is in graph
func (g *Graph) HasRelation(e *Edge) bool {
	if _, ok := g.vetexMap[e.from]; ok {
		return true
	}
	if _, ok := g.vetexMap[e.to]; ok {
		return true
	}

	return false
}

//DFS check id is in graph
func (g *Graph) DFS() {

}

//BFS check id is in graph
func (g *Graph) BFS() {

}

func gridDfs(grid [][]byte, i int, j int) {
	rows := len(grid)
	cols := len(grid[0])

	if i < 0 {
		return
	}
	if j < 0 {
		return
	}
	if i >= rows {
		return
	}
	if j >= cols {
		return
	}
	if grid[i][j] == '0' {
		return
	}

	grid[i][j] = '0'

	// up
	gridDfs(grid, i-1, j)
	// down
	gridDfs(grid, i+1, j)
	// right
	gridDfs(grid, i, j+1)
	// left
	gridDfs(grid, i, j-1)
	return
}

// NumIslands NumIslands
func NumIslands(grid [][]byte) int {
	rows := len(grid)
	if rows == 0 {
		return 0
	}
	cols := len(grid[0])
	if cols == 0 {
		return 0
	}
	numIslands := 0
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] == '1' {
				numIslands++
				gridDfs(grid, i, j)
			}
		}
	}
	return numIslands
}

func printShortestPath(path []string) {
	fmt.Println()
	for _, v := range path {
		fmt.Printf(" %v ->", v)
	}
	fmt.Println()
}

// Cord cord
type Cord struct {
	X int
	Y int
}

func shortestPath2(grid [][]int, i int, j int, k int, path []Cord, shortestPathLen *int, visited [][]int) {
	rows := len(grid)
	cols := len(grid[0])

	if i < 0 {
		return
	}
	if j < 0 {
		return
	}
	if i >= rows {
		return
	}
	if j >= cols {
		return
	}
	if visited[i][j] == 1 {
		return
	}
	visited[i][j] = 1
	if grid[i][j] == 1 {
		if k == 0 {
			//fmt.Println(path)
			visited[i][j] = 0
			return
		}
		k--
	}
	point := Cord{i, j}
	path = append(path, point)
	if *shortestPathLen != 0 && len(path) >= *shortestPathLen {
		visited[i][j] = 0
		return
	}

	// right
	shortestPath2(grid, i, j+1, k, path, shortestPathLen, visited)
	// down
	shortestPath2(grid, i+1, j, k, path, shortestPathLen, visited)
	// left
	shortestPath2(grid, i, j-1, k, path, shortestPathLen, visited)
	// up
	shortestPath2(grid, i-1, j, k, path, shortestPathLen, visited)
	if i == rows-1 && j == cols-1 {
		// reach target
		//fmt.Println(path)
		if *shortestPathLen == 0 || len(path) < *shortestPathLen {
			*shortestPathLen = len(path)
			visited[i][j] = 0
			return
		}
	}
	visited[i][j] = 0
	return
}

// ShortestPath ShortestPath
func ShortestPath(grid [][]int, k int) int {
	rows := len(grid)
	if rows == 0 {
		return 0
	}
	cols := len(grid[0])
	if cols == 0 {
		return 0
	}
	if k >= rows+cols-3 {
		return rows + cols - 2
	}
	k = int(math.Min(float64(k), float64(rows+cols-3)))
	shortestPathLen := 0
	path := make([]Cord, 0)

	visited := make([][]int, rows)
	for i := 0; i < rows; i++ {
		visited[i] = make([]int, cols)
	}

	shortestPath2(grid, 0, 0, k, path, &shortestPathLen, visited)

	return shortestPathLen - 1
}
